package similarity;

import java.io.File;
import java.util.HashMap;

import org.dom4j.Document;
import org.dom4j.DocumentException;
import org.dom4j.Element;
import org.dom4j.Node;
import org.dom4j.io.SAXReader;

import preprocess.XMLContracter;
import preprocess.XMLDoc;
import utils.Configuration;

/**
 * a very simple method to calculate similarity of XML Document, only three
 * action can be done: 1. relabel, 2. delete a leaf node, 3. insert a leaf node
 * 
 * @author huangcd
 * 
 */
public class SimpleTEDSimilarity implements Similarity
{
    private static HashMap<XMLDoc, HashMap<XMLDoc, Double>> resultMap;
    private XMLDoc                                          doc1;
    private XMLDoc                                          doc2;

    public SimpleTEDSimilarity()
    {
    }

    private static void addResult(XMLDoc doc1, XMLDoc doc2, double result)
    {
        if (!Configuration.cacheXML)
            return;
        if (resultMap == null)
            resultMap = new HashMap<XMLDoc, HashMap<XMLDoc, Double>>();

        if (!resultMap.containsKey(doc1))
            resultMap.put(doc1, new HashMap<XMLDoc, Double>());
        resultMap.get(doc1).put(doc2, result);

        if (!resultMap.containsKey(doc2))
            resultMap.put(doc2, new HashMap<XMLDoc, Double>());
        resultMap.get(doc2).put(doc1, result);
    }

    private static double getResult(XMLDoc doc1, XMLDoc doc2)
    {
        if (!Configuration.cacheXML)
            return -1;
        if (resultMap == null)
            return -1;
        if (!resultMap.containsKey(doc1))
            return -1;
        HashMap<XMLDoc, Double> tmp = resultMap.get(doc1);
        if (!tmp.containsKey(doc2))
            return -1;
        return tmp.get(doc2);
    }

    @Override
    public double calcSimilarity(XMLDoc doc1, XMLDoc doc2)
    {
        double result = getResult(doc1, doc2);
        if (result != -1)
            return result;
        this.doc1 = doc1;
        this.doc2 = doc2;
        Element root1 = doc1.getRoot();
        Element root2 = doc2.getRoot();
        double distance = calculateDistance(root1, root2);
        // System.out.println(distance);
        double size = doc1.getDescendantCount(root1) + 1
                + doc2.getDescendantCount(root2) + 1;
        result = Math.sqrt(1 - distance * distance / size / size);
        if (0 <= result && result <= 1)
            addResult(doc1, doc2, result);
        else
        {
            System.err.println("calc error:");
            new Throwable().printStackTrace(System.err);
        }
        return result;
    }

    /*
     * calculate the distance of the two given tree. delete and insert operate
     * can only be done in leaf node
     * 
     * @param e1
     * 
     * @param e2
     * 
     * @return
     */
    private double calculateDistance(Element e1, Element e2)
    {
        // String key = e1.toString() + e2.toString();
        // if (this.similaritiesMap.containsKey(key))
        // return similaritiesMap.get(key);

        int e1ChildCount = e1.nodeCount();
        int e2ChildCount = e2.nodeCount();
        double[][] D = new double[e1ChildCount + 1][e2ChildCount + 1];
        D[0][0] = updateCost(e1, e2);
        for (int i = 1; i <= e1ChildCount; i++)
        {
            Node n = e1.node(i - 1);
            D[i][0] = D[i - 1][0] + getDescendantCount(n) + 1;
        }
        for (int i = 1; i <= e2ChildCount; i++)
        {
            Node n = e2.node(i - 1);
            D[0][i] = D[0][i - 1] + getDescendantCount(n) + 1;
        }
        for (int i = 1; i <= e1ChildCount; i++)
        {
            Node c1 = e1.node(i - 1);
            for (int j = 1; j <= e2ChildCount; j++)
            {
                Node c2 = e2.node(j - 1);
                double subTreeDistance = 0;
                // 两个都不是Element，编辑距离是update的消耗
                if (!(c1 instanceof Element) && !(c2 instanceof Element))
                {
                    subTreeDistance = updateCost(c1, c2);
                }
                // 两个都是Element，编辑距离直接是树编辑距离
                else if ((c1 instanceof Element) && (c2 instanceof Element))
                {
                    subTreeDistance = calculateDistance((Element) c1,
                            (Element) c2);
                }
                // 一个是Element，另一个不是。编辑距离相当于把Element为跟的子树删除，然后再变成另外一个非Element节点
                else
                {
                    subTreeDistance = Math.max(getDescendantCount(c1) + 2,
                            getDescendantCount(c2) + 2);
                }
                D[i][j] = Math.min(Math.min(D[i - 1][j - 1] + subTreeDistance,
                        D[i][j - 1] + getDescendantCount(c2) + 1), D[i - 1][j]
                        + getDescendantCount(c1) + 1);
            }
        }

        double value = D[e1ChildCount][e2ChildCount];
        // this.similaritiesMap.put(key, value);
        return value;
    }

    private int getDescendantCount(Node n)
    {
        return Math.max(doc1.getDescendantCount(n), doc2.getDescendantCount(n));
    }

    private double updateCost(Node n1, Node n2)
    {
        if (n1.getNodeType() != n2.getNodeType())
            return 2;
        if (n1 instanceof Element && n2 instanceof Element)
            return n1.getName().equals(n2.getName()) ? 0 : 1;
        return 1;
    }

    public static void main(String[] args) throws DocumentException
    {
        SAXReader reader = new SAXReader();
        Document d1 = reader.read(new File("treeT1.xml"));
        Document d2 = reader.read(new File("treeT2.xml"));
        XMLContracter contracter = new XMLContracter();
        d1 = contracter
                .contract(d1, XMLContracter.TEXT | XMLContracter.NESTING);
        d2 = contracter
                .contract(d2, XMLContracter.TEXT | XMLContracter.NESTING);
        // XMLTree.showTree(d1);
        // XMLTree.showTree(d2);
        XMLDoc doc1 = new XMLDoc(d1, "T1");
        XMLDoc doc2 = new XMLDoc(d2, "T2");
        System.out
                .println(new SimpleTEDSimilarity().calcSimilarity(doc1, doc2));
        System.out
                .println(new SimpleTEDSimilarity().calcSimilarity(doc1, doc2));
    }
}
